#include<iostream>
#include<vector>
using namespace std;
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        //首先遍历原数组将小于0的数字变成数组的长度+1
        int  n = nums.size();
        for(int i = 0;i<n;i++)
        {
            if(nums[i]<=0)
            {
                nums[i] = n+1;
            }
        }
        //然后去遍历数组，给符合要求的数字下标打上标记
        for(int i = 0;i<n;i++)
        {
            int num = abs(nums[i]);//防止负数的出现
            if(num<=n)
            {
                nums[num-1] = -abs(nums[num-1]);//给这个数字增加符号，加上一个绝对值
                //防止重复的负号添加
            }
            //说明nums[i]这个数字是不符合条件的数字
        }
        //最后去遍历原数组，找到第一个不为负数的下标，
        int ret = -1;//等于-1是为了解决全是合法区间的情况
        for(int i = 0;i<nums.size();i++)
        {
            if(nums[i]>0)
            {
                return i+1;
            }
        }
        //说明整个数组都是合法区间就返回数组的长度+1
        return nums.size()+1;
    }
};